function Dictionary() {
  var items = {};
  this.has = function (key) {
    return key in items;
  }
  this.set = function (key, value) {
    items[key] = value; //{1} 
  }
  this.remove = function (key) {
    if (this.has(key)) {
      delete items[key];
      return true;
    }
    return false;
  }
  this.get = function (key) {
    return this.has(key) ? items[key] : undefined;
  };
  this.values = function () {
    var values = {};
    for (var k in items) { //{1} 
      if (this.has(k)) {
        values.push(items[k]); //{2} 
      }
    }
    return values;
  };
}
function Queue() {
  //这里是属性和方法
  var items = [];
  this.enqueue = function (element) {
    items.push(element);
  };
  this.dequeue = function () {
    return items.shift();
  };
  this.isEmpty = function () {
    return items.length == 0;
  };
}
function Stack() {
  var items = [];
  this.push = function (element) {
    items.push(element);
  };
  this.pop = function () {
    return items.pop();
  };
  this.peek = function () {
    return items[items.length - 1];
  };
  this.isEmpty = function () {
    return items.length == 0;
  };
  this.size = function () {
    return items.length;
  };
  this.clear = function () {
    items = [];
  };
  this.print = function () {
    console.log(items.toString());
  };
}
// 声明图类的骨架
function Graph() {
  var vertices = []; //{1} 
  var adjList = new Dictionary(); //{2} 

  this.addVertex = function (v) {
    vertices.push(v); //{3} 
    adjList.set(v, []); //{4} 
  };
  this.addEdge = function (v, w) {
    adjList.get(v).push(w); //{5}
    adjList.get(w).push(v); //{6} 
  };
  this.toString = function () {
    var s = '';
    for (var i = 0; i < vertices.length; i++) { //{10} 
      s += vertices[i] + ' -> ';
      var neighbors = adjList.get(vertices[i]); //{11} 
      for (var j = 0; j < neighbors.length; j++) { //{12} 
        s += neighbors[j] + ' ';
      }
      s += '\n'; //{13} 
    }
    return s;
  };

  var initializeColor = function () {
    var color = [];
    for (var i = 0; i < vertices.length; i++) {
      color[vertices[i]] = 'white'; //{1} 
    }
    return color;
  };

  this.bfs = function (v, callback) {
    var color = initializeColor(), //{2} 
      queue = new Queue(); //{3} 
    queue.enqueue(v); //{4} 
    while (!queue.isEmpty()) { //{5} 
      var u = queue.dequeue(), //{6} 
        neighbors = adjList.get(u); //{7}
      color[u] = 'grey'; // {8} 
      for (var i = 0; i < neighbors.length; i++) { // {9} 
        var w = neighbors[i]; // {10} 
        if (color[w] === 'white') { // {11} 
          color[w] = 'grey'; // {12} 
          queue.enqueue(w); // {13} 
        }
      }
      color[u] = 'black'; // {14} 
      if (callback) { // {15} 
        callback(u);
      }
    }
  };

  // 寻找最短路径
  this.BFS = function (v) {
    var color = initializeColor(),
      queue = new Queue(),
      d = [], //{1} 
      pred = []; //{2} 
    queue.enqueue(v);
    for (var i = 0; i < vertices.length; i++) { //{3} 
      d[vertices[i]] = 0; //{4} 
      pred[vertices[i]] = null; //{5}
    }
    while (!queue.isEmpty()) {
      var u = queue.dequeue(),
        neighbors = adjList.get(u);
      color[u] = 'grey';
      for (i = 0; i < neighbors.length; i++) {
        var w = neighbors[i];
        if (color[w] === 'white') {
          color[w] = 'grey';
          d[w] = d[u] + 1; //{6} 
          pred[w] = u; //{7} 
          queue.enqueue(w);
        }
      }
      color[u] = 'black';
    }
    return { //{8} 
      distances: d,
      predecessors: pred
    };
  };

  this.dfs = function (callback) {
    var color = initializeColor(); //{1}
    for (var i = 0; i < vertices.length; i++) { //{2} 
      if (color[vertices[i]] === 'white') { //{3} 
        dfsVisit(vertices[i], color, callback); //{4} 
      }
    }
  };
  var dfsVisit = function (u, color, callback) {
    color[u] = 'grey'; //{5} 
    if (callback) { //{6} 
      callback(u);
    }
    var neighbors = adjList.get(u); //{7} 
    for (var i = 0; i < neighbors.length; i++) { //{8} 
      var w = neighbors[i]; //{9} 
      if (color[w] === 'white') { //{10} 
        dfsVisit(w, color, callback); //{11} 
      }
    }
    color[u] = 'black'; //{12} 
  };
  var time = 0; //{1} 
  this.DFS = function () {
    var color = initializeColor(), //{2} 
      d = [],
      f = [],
      p = [];
    time = 0;
    for (var i = 0; i < vertices.length; i++) { //{3} 
      f[vertices[i]] = 0;
      d[vertices[i]] = 0;
      p[vertices[i]] = null;
    }
    for (i = 0; i < vertices.length; i++) {
      if (color[vertices[i]] === 'white') {
        DFSVisit(vertices[i], color, d, f, p);
      }
    }
    return { //{4} 
      discovery: d,
      finished: f,
      predecessors: p
    };
  };
  var DFSVisit = function (u, color, d, f, p) {
    console.log('discovered ' + u);
    color[u] = 'grey';
    d[u] = ++time; //{5} 
    var neighbors = adjList.get(u);
    for (var i = 0; i < neighbors.length; i++) {
      var w = neighbors[i];
      if (color[w] === 'white') {
        p[w] = u; // {6} 
        DFSVisit(w, color, d, f, p);
      }
    }
    color[u] = 'black';
    f[u] = ++time; //{7} 
    console.log('explored ' + u);
  };
}
//  我们使用一个数组来存储图中所有顶点的名字（行{1}），以及一个字典（在第7章中已经实
//  现）来存储邻接表（行{2}）。字典将会使用顶点的名字作为键，邻接顶点列表作为值。vertices
//  数组和adjList字典两者都是我们Graph类的私有属性。
var graph = new Graph();
var myVertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']; //{7} 
for (var i = 0; i < myVertices.length; i++) { //{8} 
  graph.addVertex(myVertices[i]);
}
graph.addEdge('A', 'B'); //{9} 
graph.addEdge('A', 'C');
graph.addEdge('A', 'D');
graph.addEdge('C', 'D');
graph.addEdge('C', 'G');
graph.addEdge('D', 'G');
graph.addEdge('D', 'H');
graph.addEdge('B', 'E');
graph.addEdge('B', 'F');
graph.addEdge('E', 'I');

console.log(graph.toString());


// 和树数据结构类似，我们可以访问图的所有节点。有两种算法可以对图进行遍历：广度优先
// 搜索（Breadth-First Search，BFS）和深度优先搜索（Depth-First Search，DFS）。图遍历可以用来
// 寻找特定的顶点或寻找两个顶点之间的路径，检查图是否连通，检查图是否含有环等。
// 在实现算法之前，让我们来更好地理解一下图遍历的思想方法。
// 图遍历算法的思想是必须追踪每个第一次访问的节点，并且追踪有哪些节点还没有被完全探
// 索。对于两种图遍历算法，都需要明确指出第一个被访问的顶点。
// 完全探索一个顶点要求我们查看该顶点的每一条边。对于每一条边所连接的没有被访问过的
// 顶点，将其标注为被发现的，并将其加进待访问顶点列表中。
// 为了保证算法的效率，务必访问每个顶点至多两次。连通图中每条边和顶点都会被访问到。
// 广度优先搜索算法和深度优先搜索算法基本上是相同的，只有一点不同，那就是待访问顶点
// 列表的数据结构。
// 算 法 数据结构 描 述
// 深度优先搜索 栈 通过将顶点存入栈中（在第3章中学习过），顶点是沿着路径被探索的，存在新的相
// 邻顶点就去访问
// 广度优先搜索 队列 通过将顶点存入队列中（在第4章中学习过），最先入队列的顶点先被探索
// 当要标注已经访问过的顶点时，我们用三种颜色来反映它们的状态。
//  白色：表示该顶点还没有被访问。
//  灰色：表示该顶点被访问过，但并未被探索过。
//  黑色：表示该顶点被访问过且被完全探索过。
// 这就是之前提到的务必访问每个顶点最多两次的原因。


// 广度优先搜索
// 广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访
// 问图的一层。换句话说，就是先宽后深地访问顶点，如下图所示：

// (1) 创建一个队列Q。
// (2) 将v标注为被发现的（灰色），并将v入队列Q。
// (3) 如果Q非空，则运行以下步骤：
//   (a) 将u从Q中出队列；
//   (b) 将标注u为被发现的（灰色）；
//   (c) 将u所有未被访问过的邻点（白色）入队列；
//   (d) 将u标注为已被探索的（黑色）。

function printNode(value) { //{16} 
  console.log('Visited vertex: ' + value); //{17} 
}
graph.bfs(myVertices[0], printNode); //{18}

var shortestPathA = graph.BFS(myVertices[0]);
console.log(shortestPathA);


var fromVertex = myVertices[0]; //{9} 
for (var i = 1; i < myVertices.length; i++) { //{10} 
  var toVertex = myVertices[i], //{11} 
    path = new Stack(); //{12} 
  for (var v = toVertex; v !== fromVertex;
    v = shortestPathA.predecessors[v]) { //{13} 
    path.push(v); //{14} 
  }
  path.push(fromVertex); //{15} 
  var s = path.pop(); //{16} 
  while (!path.isEmpty()) { //{17} 
    s += ' - ' + path.pop(); //{18} 
  }
  console.log(s); //{19} 
}

// 深度优先搜索
// 深度优先搜索算法不需要一个源顶点。在深度优先搜索算法中，若图中顶点v未访问，则访
// 问该顶点v。
// (1) 标注v为被发现的（灰色）。
// (2) 对于v的所有未访问的邻点w：
//     (a) 访问顶点w。
// (3) 标注v为已被探索的（黑色）。
graph.DFS()